{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Middle of the Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: middleNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #链表的中间结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你单链表的头结点 <code>head</code> ，请你找出并返回链表的中间结点。</p>\n",
    "\n",
    "<p>如果有两个中间结点，则返回第二个中间结点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-midlist1.jpg\" style=\"width: 544px; height: 65px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5]\n",
    "<strong>输出：</strong>[3,4,5]\n",
    "<strong>解释：</strong>链表只有一个中间结点，值为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg\" style=\"width: 664px; height: 65px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5,6]\n",
    "<strong>输出：</strong>[4,5,6]\n",
    "<strong>解释：</strong>该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表的结点数范围是 <code>[1, 100]</code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [middle-of-the-linked-list](https://leetcode.cn/problems/middle-of-the-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [middle-of-the-linked-list](https://leetcode.cn/problems/middle-of-the-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[1,2,3,4,5,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None:\n",
    "            return None\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow  = slow.next\n",
    "            fast = fast.next.next\n",
    "        if fast:\n",
    "            return slow.next\n",
    "        else:\n",
    "            return slow\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        node1 = head\n",
    "        node2 = head\n",
    "        while node2 and node2.next:\n",
    "            node1 = node1.next\n",
    "            node2 = node2.next.next\n",
    "        return node1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast  and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        slow, fast = head, head\n",
    "        while((fast!=None) and (fast.next!=None)):\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: 'ListNode') -> 'ListNode':\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head):\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        node = ListNode(None)\n",
    "        node.next = head\n",
    "        fast = slow = node\n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next if fast.next else fast.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "  def middleNode(self, head):\n",
    "    if(head == None):\n",
    "      return None\n",
    "    pointer1 = head\n",
    "    pointer2 = head\n",
    "    while(pointer2 != None and pointer2.next != None):\n",
    "      pointer1 = pointer1.next\n",
    "      pointer2 = pointer2.next.next\n",
    "    return pointer1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        # li = []\n",
    "        # while head:\n",
    "        #     li.append(head.val)\n",
    "        #     head = head.next\n",
    "\n",
    "        # mid = len(li) // 2\n",
    "        # li = li[mid:]\n",
    "        # head = ListNode(li[0])\n",
    "        # tail = head\n",
    "        # for i in li[1:]:\n",
    "        #     node = ListNode(i)\n",
    "        #     tail.next = node\n",
    "        #     tail = node\n",
    "        # return head\n",
    " \n",
    "        #法二：遍历链表写入列表\n",
    "        #链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N，对应的中间节点即为 A[N/2]\n",
    "\n",
    "        # A = [head] #把链表写进列表里\n",
    "        # while A[-1].next:\n",
    "        #     A.append(A[-1].next)\n",
    "        # return A[len(A) // 2]\n",
    "        \n",
    "        #法三：快慢指针法\n",
    "        #我们可以继续优化方法二，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。\n",
    "\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        length = 0\n",
    "        cur = head\n",
    "        while cur:\n",
    "            length += 1\n",
    "            cur = cur.next\n",
    "        length = length//2+1\n",
    "        cur = head\n",
    "        while length-1:\n",
    "            cur = cur.next\n",
    "            length -= 1\n",
    "        return cur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        if not head: ## 判空\n",
    "            return None\n",
    "\n",
    "        if head != None and head.next == None: ## 如果仅存在头结点\n",
    "            return head\n",
    "\n",
    "        ## 快慢指针\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "\n",
    "        while fast and fast.next: ## 快指针是慢指针速度的两倍，直到快指针走到None，或者最后一个\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        if not fast: ## 如果快指针走到None，说明慢指针此时为中间结点\n",
    "            return slow\n",
    "        \n",
    "        if not fast.next: ## 如果快指针走到最后一个结点，说明慢指针的下一个是中间结点\n",
    "            return slow.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        slow = head\n",
    "        fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "\n",
    "        return slow\n",
    "\n",
    "class Solutions:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        if not head:\n",
    "            return None\n",
    "\n",
    "        if head != None and head.next == None:\n",
    "            return head\n",
    "\n",
    "        slow = head\n",
    "        fast = head.next\n",
    "\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        if not fast:\n",
    "            return slow\n",
    "        \n",
    "        if not fast.next:\n",
    "            return slow.next\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        from copy import deepcopy\n",
    "        l1, l2 = deepcopy(head), deepcopy(head)\n",
    "        while l2.next:\n",
    "            if l2.next.next:\n",
    "                l1 = l1.next\n",
    "                l2 = l2.next.next\n",
    "            else:\n",
    "                break\n",
    "        print(l2)\n",
    "        if l2.next:\n",
    "            return l1.next\n",
    "        return l1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "import copy\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        ans=copy.deepcopy(head)\n",
    "        i=1\n",
    "        while ans.next:\n",
    "          i+=1\n",
    "          ans=ans.next\n",
    "        if i%2==1:\n",
    "          index=(i+1)/2-1\n",
    "        else:\n",
    "          index=i/2\n",
    "        j=0\n",
    "        res=head\n",
    "        while j<index:\n",
    "          if res.next:\n",
    "            res=res.next\n",
    "          j+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            fast, slow = fast.next.next, slow.next\n",
    "        return slow\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        Mid = head\n",
    "        time = 0\n",
    "\n",
    "        while(head):\n",
    "            time += 1\n",
    "            if time == 2: \n",
    "                time = 0\n",
    "                Mid = Mid.next\n",
    "            head = head.next\n",
    "\n",
    "        return Mid \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\r\n",
    "# class ListNode:\r\n",
    "#     def __init__(self, val=0, next=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.next = next\r\n",
    "class Solution:\r\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\r\n",
    "        fast = head\r\n",
    "        slow = head\r\n",
    "        while fast and fast.next:\r\n",
    "            fast = fast.next.next\r\n",
    "            slow = slow.next\r\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        a=head\n",
    "        b=head\n",
    "        while(b):\n",
    "            b=b.next\n",
    "            if b:\n",
    "                a=a.next\n",
    "                b=b.next\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow, fast = head, head\n",
    "        while fast and fast.next:\n",
    "            print(slow, fast,'\\n')\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head.next:\n",
    "            return head\n",
    "\n",
    "        pos1_code = None\n",
    "        pos2_node = None\n",
    "        tag = True\n",
    "\n",
    "        head_copy = copy.deepcopy(head)\n",
    "\n",
    "        while head_copy.next:\n",
    "            if tag:\n",
    "                pos1_code = head.next\n",
    "                pos2_node = head_copy.next\n",
    "                head = head.next\n",
    "                head_copy = head_copy.next\n",
    "                tag = False\n",
    "            else:\n",
    "                pos2_node = head_copy.next\n",
    "                head_copy = head_copy.next\n",
    "                tag = True\n",
    "        return pos1_code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "            slow = head\n",
    "            fast = head\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        fast = slow = head\n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "        return slow"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
